Search

Adequate rings and, in particular, adequate elements appear as a generalization of principal ideal rings in the investigation of the problem of matrix reduction. The main property of elements of these rings is the possibility of their representation in the form of the product of two factors satisfying certain conditions. We introduce the notion of adequacy in the case of noncommutative rings and study the properties of matrix divisors over the adequate rings. We also analyze the influence of changes in the Smith normal forms and transforming matrices on the adequate properties of matrix divisors. [ABSTRACT FROM AUTHOR]

In this paper, we provide an explicit formula for the rank of the walk matrix of the extended Dynkin graph D ˜ n. Moreover, we prove that the Smith normal form of the walk matrix of the extended Dynkin graph D ˜ n is { diag ( 1 , ... , 1 ︸ r − 1 , n − 1 2 , 0 , ... , 0) , if n is odd, diag ( 1 , ... , 1 ︸ r − 1 , n − 1 , 0 , ... , 0) , if n is even, where r = ⌊ n 2 ⌋. [ABSTRACT FROM AUTHOR]

Let p stand for an odd prime and let η ∈ Z+ (the set of positive integers). Let Fq denote the finite field having q = pη elements and F*q = Fq\{0}. In this paper, when the determinants of exponent matrices are coprime to q - 1, we use the Smith normal form of exponent matrices to derive exact formulas for the numbers of rational points on the affine varieties over Fq defined by ... respectively, where dij, ei'j' ∈ Z+, ai, ci' ∈ F*q, i = 1,..., s + t, j = 1, ..., n, i' = 1,..., r + k + w, j' = 1,..., m, and b1, b2, l1, l2, l3 ∈ Fq. These formulas extend the theorems obtained by Q. Sun in 1997. Our results also give a partial answer to an open question posed by S.N. Hu, S.F. Hong and W. Zhao [The number of rational points of a family of hypersurfaces over finite fields, J. Number Theory 156 (2015), 135-153]. [ABSTRACT FROM AUTHOR]

For nonsingular matrices of arbitrary order over a commutative principal ideal domain under certain restrictions imposed on their canonical diagonal forms, we construct the Smith normal form of their least common right multiple. [ABSTRACT FROM AUTHOR]

Let 픽 q be the finite field of odd characteristic p with q elements ( q = p n , n ∈ ℕ ) and let 픽 q * represent the set of nonzero elements of 픽 q . By making use of the Smith normal form of exponent matrices, we obtain an explicit formula for the number of rational points on the variety defined by the following system of equations over 픽 q : { ∑ i = 1 r a i (1) ⁢ x 1 e i ⁢ 1 (1) ⁢ ⋯ ⁢ x n e i ⁢ n (1) = b 1 , ∑ j ′ = 0 t - 1 ∑ i ′ = 1 r j ′ + 1 - r j ′ a r j ′ + i ′ (2) ⁢ x 1 e r j ′ + i ′ , 1 (2) ⁢ ⋯ ⁢ x n j ′ + 1 e r j ′ + i ′ , n j ′ + 1 (2) = b 2 , where b i ∈ 픽 q ( i = 1 , 2 ), t ∈ ℕ , 0 = n 0 < n 1 < n 2 < ⋯ < n t , n k - 1 < n ≤ n k for some 1 ≤ k ≤ t , 0 = r 0 < r 1 < r 2 < ⋯ < r t , a i (1) ∈ 픽 q * for i ∈ { 1 , ... , r } , a i ′ (2) ∈ 픽 q * for i ′ ∈ { 1 , ... , r t } , and the exponent of each variable is a positive integer. This generalizes the results obtained previously by Wolfmann, Sun, Cao, and others. Our result also gives a partial answer to an open problem raised by Hu, Hong and Zhao [S. N. Hu, S. F. Hong and W. Zhao, The number of rational points of a family of hypersurfaces over finite fields, J. Number Theory 156 2015, 135–153]. [ABSTRACT FROM AUTHOR]

We prove that the walk matrix of the Dynkin graph D n has the Smith normal form diag [ 1 , 1 , ... , 1 ︸ n 2 − 1 , 2 , 2 , ... , 2 ︸ n 2 − 1 , 0 , 0 ] when n ≡ 0 (mod 4). This gives an affirmative answer to a question in (Wang et al., 2022 [22]). [ABSTRACT FROM AUTHOR]

In this paper, we revisit the greatest common right divisor (GCRD) extraction from a set of polynomial matrices ... with coefficients in a generic field F and with common column dimension n. We give necessary and sufficient conditions for a matrix G(λ)∈F[λ]]lxn to be a GCRD using the Smith normal form of the m x n compound matrix P(λ) obtained by concatenating Pi(λ) vertically, where ... We also describe the complete set of degrees of freedom for the solution G(λ), and we link it to the Smith form and Hermite form of P(λ). We then give an algorithm for constructing a particular minimum size solution for this problem when F=C or R, using state-space techniques. This new method works directly on the coefficient matrices of P(λ)., using orthogonal transformations only. The method is based on the staircase algorithm, applied to a particular pencil derived from a generalized state-space model of P(λ). [ABSTRACT FROM AUTHOR]

This work is a continuation of our previous work [D. M. Ha and H. T. Ngo. Int. J. Math., 34 (2023)], studying the expanding phenomenon in matrices over a finite chain ring with large residue field. A sum-product estimate is proved. It is shown that xy+z+t is a very strong expander, and that x(y + z) and xyz + x are moderate expanders of exponent 13. These results generalize the works of Le and Nguyen (see [J. Number. Theory, 216 (2020), pp. 174--191] and [Discrete Appl. Math., 322 (2022), pp. 166--170]. The solvability in large subsets of the equation xy = z + t is obtained, providing an answer to a question raised by Gyarmati and S\'ark\"ozy [Acta Math. Hungar., 119 (2008), pp. 259--280]. The proofs use spectral graph theory and elementary divisor theory. [ABSTRACT FROM AUTHOR]

The equivalence of systems is a crucial concept in multidimensional systems. The Smith normal forms of multivariate polynomial matrices play important roles in the theory of polynomial matrices. In this paper, we mainly study the unimodular equivalence of some special kinds of multivariate polynomial matrices and obtain some tractable criteria under which such matrices are unimodular equivalent to their Smith normal forms. We propose an algorithm for reducing such n D polynomial matrices to their Smith normal forms and present an example to illustrate the availability of the algorithm. Furthermore, we extend the results to the non-square case. [ABSTRACT FROM AUTHOR]

A Las Vegas randomized algorithm is given to compute the Smith multipliers for a nonsingular integer matrix A , that is, unimodular matrices U and V such that A V = U S , with S the Smith normal form of A. The expected running time of the algorithm is about the same as required to multiply together two matrices of the same dimension and size of entries as A. Explicit bounds are given for the size of the entries in both unimodular multipliers. The main tool used by the algorithm is the Smith massager, a relaxed version of V , the unimodular matrix specifying the column operations of the Smith computation. From the perspective of efficiency, the main tools used are fast linear system solving and partial linearization of integer matrices. As an application of the Smith with multipliers algorithm, a fast algorithm is given to find the fractional part of the inverse of the input matrix. [ABSTRACT FROM AUTHOR]

The first extended greatest common right divisor (GCRD) algorithm for parametric univariate polynomial matrices is presented. The starting point of this GCRD algorithm is the free property of submodules over univariate polynomial rings. We convert the computation of GCRDs to that of free basis for modules and prove that a free basis of the submodule generated by row vectors of input matrices forms just a GCRD of these matrices. The GCRD algorithm is obtained by computing a minimal Gröbner basis for the corresponding submodule since a minimal Gröbner basis of submodules is a free basis for univariate cases. While the key idea of extended algorithm is to construct a special module by adding the unit vectors which can record the representation coefficients. This method based on modules can be naturally generalized to the parametric case because of the comprehensive Gröbner systems for modules. As a consequence, we obtain an extended GCRD algorithm for parametric univariate polynomial matrices. More importantly, we apply the proposed extended GCD algorithm for univariate polynomials (as a special case of matrices) to the computation of Smith normal form, and give the first algorithm for reducing a univariate polynomial matrix with parameters to its Smith normal form. [ABSTRACT FROM AUTHOR]

Let W (D n) denote the walk matrix of the Dynkin graph D n (n ≥ 4), a tree obtained from the path of order n − 1 by adding a pendant edge at the second vertex. We prove that rank W (D n) = n − 2 if 4 | n and rank W (D n) = n − 1 otherwise. Furthermore, we prove that the Smith normal form of W (D n) is diag [ 1 , 1 , ... , 1 ︸ ⌈ n 2 ⌉ , 2 , 2 , ... , 2 ︸ ⌊ n 2 ⌋ − 1 , 0 ] when 4 ∤ n. This confirms a recent conjecture in [W. Wang, F. Liu, W. Wang, Generalized spectral characterizations of almost controllable graphs, European J. Combin. 96(2021): 103348]. [ABSTRACT FROM AUTHOR]

We introduce the concept of codeterminantal graphs, which generalize the concepts of cospectral and coinvariant graphs. To do this, we investigate the relationship of the spectrum and the Smith normal form (SNF) with the determinantal ideals. We establish a necessary and sufficient condition for graphs to be codeterminantal on R [ x ] , and we present some computational results on codeterminantal graphs up to 9 vertices. Finally, we show that complete graphs and star graphs are determined by the SNF of its distance Laplacian matrix. [ABSTRACT FROM AUTHOR]

The equivalence of systems is a crucial concept in multidimensional systems. The Smith normal forms of multivariate polynomial matrices play important roles in the theory of polynomial matrices. In this paper, we mainly study the unimodular equivalence of some special kinds of multivariate polynomial matrices and obtain some tractable criteria under which such matrices are unimodular equivalent to their Smith normal forms. We propose an algorithm for reducing such nD polynomial matrices to their Smith normal forms and present an example to illustrate the availability of the algorithm. Furthermore, we extend the results to the non-square case.

Let R be a ring and let (a 1 , ... , a n) ∈ R n be a unimodular vector, where n ≥ 2 and each a i is in the center of R. Consider the linear equation a 1 X 1 + ⋯ + a n X n = 0 , with solution set S. Then S = S 1 + ⋯ + S n , where each S i is naturally derived from (a 1 , ... , a n) , and we give a presentation of S in terms of generators taken from the S i and appropriate relations. Moreover, under suitable assumptions, we elucidate the structure of each quotient module S / S i. Furthermore, assuming that R is a principal ideal domain, we provide a simple way to construct a basis of S and, as an application, we determine the structure of the quotient module S / U i , where each U i is a specific module containing S i. [ABSTRACT FROM AUTHOR]

Let A , B be subsets of a finite abelian group G. Suppose that A + B does not contain a unique sum, i.e., there is no g ∈ G with a unique representation g = a + b , a ∈ A , b ∈ B. From such sets A , B , sparse linear systems over the rational numbers arise. We obtain a new determinant bound on invertible submatrices of the coefficient matrices of these linear systems. Under the condition that | A | + | B | is small compared to the order of G , these bounds provide essential information on the Smith Normal Form of these coefficient matrices. We use this information to prove that A and B admit coset partitions whose parts have properties resembling those of A and B. As a consequence, we improve previously known sufficient conditions for the existence of unique sums in A + B and show how our structural results can be used to classify sets A and B for which A + B does not contain a unique sum when | A | + | B | is relatively small. Our method also can be applied to subsets of abelian groups which have no unique differences. [ABSTRACT FROM AUTHOR]

For a given graph G with n vertices, the walk matrix W of G is defined as W = [ e A e A 2 e ⋯ A n − 1 e ] , where A is the adjacency matrix of the graph G and e is the vector of all ones. In this paper, we prove that for any positive integer k , at most ⌊ n 2 ⌋ invariant factors of W are congruent to 2 k modulo 2 k + 1. [ABSTRACT FROM AUTHOR]

The reduction of a multidimensional system is closely related to the reduction of a multivariate polynomial matrix, for which the Smith normal form of the matrix plays a key role. In this paper, we investigate the reduction of weakly linear multivariate polynomial matrices to their Smith normal forms. Using hierarchical-recursive method and Quillen-Suslin Theorem, we derive some necessary and sufficient conditions ensuring that such matrices can be reduced to their Smith normal forms, and these conditions are easily checked by computing the reduced Gröbner bases of the relevant polynomial ideals. Based on the new results, we propose an algorithm for reducing weakly linear multivariate polynomial matrices to their Smith normal forms. [ABSTRACT FROM AUTHOR]

We show that all elementary lattices that are free Z p C p -modules admit an orthogonal decomposition into a sum of a free unimodular and a p-modular Z p C p -lattice. [ABSTRACT FROM AUTHOR]

Cloud computing is an innovative technology to support outsourcing of computing resources on-demand. But it is lack of security, confidentiality, and privacy. This paper attempts to propose a solution to the above-said problems by a secure, confidential and Fully Homomorphic Encryption technique with the desired level of access control. The present scheme is based on symmetric keys and Smith Normal Form assures the homomorphic property. All the operations are simple matrix multiplications and consequently, the present scheme sustains the owners of the cloud to secure their private data from its uncertain clients. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices. The walk matrix W (G) of G is the matrix [ e , A e , ... , A n − 1 e ] , where A is the adjacency matrix of G and e is the all-one vector. Let W be a walk matrix of order n. We show that at most ⌊ n 2 ⌋ invariant factors of W are congruent to 2 modulo 4. As a consequence, it is proved that, for any n × n walk matrix W with 2-rank r , the determinant of W is always a multiple of 2 ⌈ 3 n − 4 r 2 ⌉. Moreover, if 2 − ⌈ 3 n − 4 r 2 ⌉ det ⁡ W is odd and square-free, then the Smith normal form of W can be recovered uniquely from the triple (n , r , det ⁡ W). [ABSTRACT FROM AUTHOR]

We consider the problem of computing the nearest matrix polynomial with a non-trivial Smith Normal Form. We show that computing the Smith form of a matrix polynomial is amenable to numeric computation as an optimization problem. Furthermore, we describe an effective optimization technique to find a nearby matrix polynomial with a non-trivial Smith form. The results are then generalized to include the computation of a matrix polynomial having a maximum specified number of ones in the Smith Form (i.e., with a maximum specified McCoy rank). We discuss the geometry and existence of solutions and how our results can be used for an error analysis. We develop an optimization-based approach and demonstrate an iterative numerical method for computing a nearby matrix polynomial with the desired spectral properties. We also describe an implementation of our algorithms and demonstrate the robustness with examples in Maple. [ABSTRACT FROM AUTHOR]

For non-singular matrices with some restrictions, we establish the relationships between Smith normal forms and transforming matrices (a invertible matrices that transform the matrix to its Smith normal form) of two matrices with corresponding matrices of their least common right multiple over a commutative principal ideal domains. Thus, for such a class of matrices, given answer to the well-known task of M. Newman. Moreover, for such matrices, received a new method for finding their least common right multiple which is based on the search for its Smith normal form and transforming matrices.

The four point theorem is a condition for distances to arise from trees. Based on this condition, for any tree T on n vertices, we associate an ( n 2 ) × ( n 2 ) matrix M T. We find the rank and the Smith Normal Form (SNF) of the matrix M T and show that it only depends on n and is independent of the structure of the tree T. Curiously, the non-zero part of the SNF of M T coincides with the SNF of the distance matrix of T. Many such "tree independent" results are known and this result is yet another such result. [ABSTRACT FROM AUTHOR]

A polynomial f in Q x , y , z is integer-valued if f (x , y , z) ∈ Z , whenever x , y , z are integers. This work will look at the case where f is homogeneous and will present algorithms for constructing polynomials f p k with f ∈ Z x , y , z such that k is as large as possible for a given degree. From this we will find bases for the modules of homogeneous integer-valued polynomials (IVPs) in a range of degrees. IVPs have been studied for their topological applications, including the homogeneous ones. We explain the connection between 3-variable homogeneous IVPs of degree m and 3-variable IVPs of degree m , as well as with 2-variable IVPs of degree m evaluated at odd values only, then use linear algebra to calculate bases for both cases in a range of degrees. [ABSTRACT FROM AUTHOR]

Distance ideals generalize the Smith normal form of the distance matrix of a graph. The family of graphs with 2 trivial distance ideals contains the family of graphs whose distance matrix has at most 2 invariant factors equal to 1. Here we give an infinite family of forbidden induced subgraphs for the graphs with 2 trivial distance ideals. These are also related with other well known graph classes. [ABSTRACT FROM AUTHOR]

Abaffy, Broyden and Spediacto (ABS) introduced a class of the so-called ABS methods to solve systems of linear equations. The ABS approach was specialized to solve linear Diophantine systems by Esmaeili, Mahdavi-Amiri and Spedicato. The method was extended to systems of certain linear inequalities to provide all solutions. Here, we mainly focus on the theoretical research into rank reduction processes for solving linear Diophantine systems and computing integer factorizations. Basic integer ABS algorithm, integer extended ABS (IEABS) algorithm, rank one perturbed problem, the generalized Rosser's approach (GRA), the extended integer rank reduction process, the integer Wedderburn rank reduction formula and the associated integer biconjugation process are studied. We present an integrated integer rank reduction process, develop various integer factorizations and show their use in solving Diophantine equations. [ABSTRACT FROM AUTHOR]

Second-order sampling has been discussed in the contexts of 2-D frequency distributions made up of two tiling clusters with lattice systems having the same periodicity, while mixed-order sampling has been discussed for those made up of tiling clusters with lattice systems having different periodicities. However, there has been no discussion when the 2-D frequency distribution is made up of a large number of tiling clusters with lattice systems having the same periodicity. This paper describes a method of finding higher-order samplings for the frequency distributions made up of one main body of frequency components and deleted components in these situations. Smith normal forms and Vandermonde determinants play an important role in this method by guaranteeing the existence of higher-order samplings and finding, in practice, the sampling positions and sampling functions. The positions and functions of fifth-order sampling of a 2-D checkerboard-shaped frequency distribution are explicitly presented as an application of the proposed method. [ABSTRACT FROM AUTHOR]

We introduce the concept of distance ideals of graphs, which can be regarded as a generalization of the Smith normal form and the spectra of the distance matrix and the Laplacian distance matrix of a graph. We also obtain a classification of the graphs with at most one trivial distance ideal. [ABSTRACT FROM AUTHOR]

We compute the elementary divisors of the adjacency and Laplacian matrices of families of polar graphs. These graphs have as vertices the isotropic one-dimensional subspaces of finite vector spaces with respect to non-degenerate forms, with adjacency given by orthogonality. [ABSTRACT FROM AUTHOR]

The critical group of a finite connected graph is an abelian group defined by the Smith normal form of its Laplacian. Let q be a power of a prime and H be a multiplicative subgroup of K = F q. By Cay (K , H) we denote the Cayley graph on the additive group of K with "connection" set H. A strongly regular graph of the form Cay (K , H) is called a cyclotomic strongly regular graph. Let ℓ > 2 and p be primes such that p is primitive (mod ℓ). We compute the critical groups of a family of cyclotomic strongly regular graphs for which q = p (ℓ − 1) t (with t ∈ N) and H is the unique multiplicative subgroup of order k = q − 1 ℓ. These graphs were first discovered by van Lint and Schrijver in [24]. [ABSTRACT FROM AUTHOR]

We study sum-of-squares representations of symmetric univariate real matrix polynomials that are positive semidefinite along the real line. We give a new proof of the fact that every positive semidefinite univariate matrix polynomial of size n × n can be written as a sum of squares M = Q T Q , where Q has size (n + 1) × n , which was recently proved by Blekherman–Plaumann–Sinn–Vinzant. Our new approach using the theory of quadratic forms allows us to prove the conjecture made by these authors that these minimal representations M = Q T Q are generically in one-to-one correspondence with the representations of the nonnegative univariate polynomial det (M) as sums of two squares. In parallel, we will use our methods to prove the more elementary hermitian analogue that every hermitian univariate matrix polynomial M that is positive semidefinite along the real line, is a square, which is known as the matrix Fejér–Riesz Theorem. [ABSTRACT FROM AUTHOR]

Spectral characterization of graphs is an important topic in spectral graph theory. An oriented graph G σ is obtained from a simple undirected graph G by assigning to every edge of G a direction so that G σ becomes a directed graph. The skew-adjacency matrix of an oriented graph G σ is a real skew-symmetric matrix S (G σ) = (s i j) , where s i j = − s j i = 1 if (i , j) is an arc; s i j = s j i = 0 otherwise. Let G σ and H τ be two oriented graphs whose skew-adjacency matrices are S (G σ) and S (H τ) , respectively. We say G σ is R -cospectral to H τ if t J − S (G σ) and t J − S (H τ) have the same spectrum for any t ∈ R , where J is the all-ones matrix. An oriented graph G σ is said to be determined by the generalized skew spectrum (DGSS for short), if any oriented graph which is R -cospectral to G σ is isomorphic to G σ. Let W (G σ) = [ e , S (G σ) e , S 2 (G σ) e , ... , S n − 1 (G σ) e ] be the skew-walk-matrix of G σ , where e is the all-ones vector. A theorem of Qiu, Wang and Wang [9] states that if G σ is a self-converse oriented graph and 2 − ⌊ n 2 ⌋ det ⁡ W (G σ) is odd and square-free, then G σ is DGSS. In this paper, based on the Smith Normal Form of the skew-walk-matrix of G σ we obtain our main result: Let q be a prime and G σ be a self-converse oriented graph on n vertices with det ⁡ W (G σ) ≠ 0. Assume that r a n k q (W (G σ)) = n − 1 if q is an odd prime, and r a n k q (W (G σ)) = ⌈ n 2 ⌉ if q = 2. If Q is a regular rational orthogonal matrix satisfying Q T S (G σ) Q = S (H τ) for some oriented graph H τ , then the level of Q divides d n (W (G σ)) q , where d n (W (G σ)) is the n -th invariant factor of W (G σ). Consequently, it leads to an easier way to prove Qiu, Wang and Wang's theorem above. [ABSTRACT FROM AUTHOR]

The paper presents a numerical procedure for relating the behaviour of two different structures, i.e. determining a scale between two structures. This novel solution is based on the notion of matrix similarity and linear transformations, with the restriction that the scale between structures is determined only after structural discretization, and that both structures have to be in the elastic regime. The structure scale can be determined in loading space or displacement space (i.e. structure forces or displacements are put into relation) where the scaling of the static structure model is based on the matrix equivalence principle, and scaling of the dynamic structure model is based on the Smith normal form. The structure scale in operator space (structure stiffness or flexibility matrices are put into relation) should be based on the Sylvester matrix equation. However, that approach is not practical and is replaced with the Levenberg-Marquardt method for obtaining only approximately equivalent stiffness matrices. Numerical examples illustrate the proposed novel approach.

Abstract We investigate the Smith Normal Form (SNF) of alternating sign matrices (ASMs) and related matrices of 0's and 1's ((0 , 1) -matrices). We identify certain classes of ASMs and (0 , 1) -matrices whose SNFs are (0 , 1) -matrices. We relate some of our work to various ranks, in particular, the (0 , 1) -rank of a (0 , 1) -matrix, that is, the bipartite partition number of a bipartite graph. [ABSTRACT FROM AUTHOR]

We show that the Smith normal form of a skew‐symmetric D‐optimal design of order n≡2(mod4) is determined by its order. Furthermore, we show that the Smith normal form of such a design can be written explicitly in terms of the order n, thereby proving a recent conjecture of Armario. We apply our result to show that certain D‐optimal designs of order n≡2(mod4) are not equivalent to any skew‐symmetric D‐optimal design. We also provide a correction to a result in the literature on the Smith normal form of D‐optimal designs. [ABSTRACT FROM AUTHOR]

Critical ideals generalize the critical group, Smith group and the characteristic polynomials of the adjacency and Laplacian matrices of a graph. We give a complete characterization of the digraphs with at most one trivial critical ideal. Which implies the characterizations of the digraphs whose critical group has one invariant factor equal to one, and the digraphs whose Smith group has one invariant factor equal to one. [ABSTRACT FROM AUTHOR]

A class of complex-valued convolutional codes, wavelet codes, that encode numbers into numbers, is constructed by assigning consecutively indexed discrete Fourier transform (DFT) vectors to the parity-checking requirements. For a rate $k/n$ code with constraint length $m$ , the parameters must satisfy (m + 1)(n-k)